#include "main/utils.h"
using namespace std;

string minSubString(const string &str1, const string &str2) {
  map<char, int> help_map;
  for (int i = 0; i < str2.size(); ++i) {
    if (help_map.find(str2[i]) == help_map.end()) {
      help_map[str2[i]] = 1;
    } else {
      ++help_map[str2[i]];
    }
  }
  int begin = 0;
  int min_begin = 0, min_end = 0;
  int min_len = INT_MAX;
  int count = help_map.size();
  for (int end = 0; end < str1.size(); ++end) {
    if (help_map.find(str1[end]) != help_map.end()) {
      --help_map[str1[end]];
      if (help_map[str1[end]] == 0) {
        --count;
      }
    }
    while (!count) {
      int cur_len = end - begin + 1;
      if (cur_len < min_len) {
        min_begin = begin;
        min_end = end;
        min_len = cur_len;
      }
      if (help_map.find(str1[begin]) != help_map.end()) {
        ++help_map[str1[begin]];
        if (help_map[str1[begin]] == 1) {
          ++count;
        }
      }
      ++begin;
    }
  }
  string ret = min_len < INT_MAX ? str1.substr(min_begin, min_len) : "";
  return ret;
}

int main() {
  string str1 = "ADDBANCAD";
  string str2 = "ABC";
  string ret = minSubString(str1, str2);
  cout << ret << endl;

  str1 = "hoggengruhige";
  str2 = "hei";
  ret = minSubString(str1, str2);
  cout << ret << endl;

  return 0;
}
